/*-------------------------------------------------------------------------
 *
 * bitmapset.c
 *	  PostgreSQL 通用位图集合包
 *
 * 位图集合可以表示任何非负整数的集合，尽管它主要用于最大
 * 值不大的集合，例如最多几百个。根据惯例，所有操作始终接
 * 收 NULL 指针以表示空集合。（但要注意这不是空集合的唯一
 * 表示。使用 bms_is_empty() 优先于测试 NULL。）
 *
 *
 * Copyright (c) 2003-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/backend/nodes/bitmapset.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "common/hashfn.h"
#include "nodes/bitmapset.h"
#include "nodes/pg_list.h"
#include "port/pg_bitutils.h"


#define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x)	((x) % BITS_PER_BITMAPWORD)

#define BITMAPSET_SIZE(nwords)	\
	(offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))

/*----------
 * 这是一个众所周知的巧妙技巧，用于隔离字中的最右边的一个比特。 这假设二的补充算术。 考虑任何非零值，关注最右边的一个。 然后这个值类似于
 *				xxxxxx10000
 * 其中x是未指定的比特。 二的补充负数是通过反转所有比特并加一形成的。 反转得到
 *				yyyyyy01111
 * 其中每个y是相应x的反转。 增加一得到
 *				yyyyyy10000
 * 然后与原始值进行与运算得到
 *				00000010000
 * 这对于所有情况都有效，除了原始值=零的情况，在这种情况下我们当然得到了零。
 *----------
 */
#define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x)))

#define HAS_MULTIPLE_ONES(x)	((bitmapword) RIGHTMOST_ONE(x) != (x))

/* 选择适当的位操作函数以适应位图字大小 */
#if BITS_PER_BITMAPWORD == 32
#define bmw_leftmost_one_pos(w)		pg_leftmost_one_pos32(w)
#define bmw_rightmost_one_pos(w)	pg_rightmost_one_pos32(w)
#define bmw_popcount(w)				pg_popcount32(w)
#elif BITS_PER_BITMAPWORD == 64
#define bmw_leftmost_one_pos(w)		pg_leftmost_one_pos64(w)
#define bmw_rightmost_one_pos(w)	pg_rightmost_one_pos64(w)
#define bmw_popcount(w)				pg_popcount64(w)
#else
#error "invalid BITS_PER_BITMAPWORD"
#endif


/*
 * bms_copy - 创建一个位图集的palloc复制
 */
Bitmapset * bms_copy(const Bitmapset *fc_a)
{
	Bitmapset  *fc_result;
	size_t		fc_size;

	if (fc_a == NULL)
		return NULL;
	fc_size = BITMAPSET_SIZE(fc_a->nwords);
	fc_result = (Bitmapset *) palloc(fc_size);
	memcpy(fc_result, fc_a, fc_size);
	return fc_result;
}

/*
 * bms_equal - 两个位图集是否相等？
 *
 * 这是真正的而非物理的相等；特别是，NULL指针将被报告为等于一个不包含任何成员的palloc值。
 */
bool bms_equal(const Bitmapset *fc_a, const Bitmapset *fc_b)
{
	const Bitmapset *fc_shorter;
	const Bitmapset *fc_longer;
	int			fc_shortlen;
	int			fc_longlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
	{
		if (fc_b == NULL)
			return true;
		return bms_is_empty(fc_b);
	}
	else if (fc_b == NULL)
		return bms_is_empty(fc_a);
	/* 确定较短和较长的输入 */
	if (fc_a->nwords <= fc_b->nwords)
	{
		fc_shorter = fc_a;
		fc_longer = fc_b;
	}
	else
	{
		fc_shorter = fc_b;
		fc_longer = fc_a;
	}
	/* 并处理 */
	fc_shortlen = fc_shorter->nwords;
	for (fc_i = 0; fc_i < fc_shortlen; fc_i++)
	{
		if (fc_shorter->words[fc_i] != fc_longer->words[fc_i])
			return false;
	}
	fc_longlen = fc_longer->nwords;
	for (; fc_i < fc_longlen; fc_i++)
	{
		if (fc_longer->words[fc_i] != 0)
			return false;
	}
	return true;
}

/*
 * bms_compare - 位图集的qsort样式比较器
 *
 * 这保证了仅当bms_equal认为它们相等时，才会报告值为相等。  否则，设置在一个值中但不在另一个值中的最高编号比特决定结果。  （这一规则意味着，例如，{6}大于{5}，这似乎是可信的。）
 */
int bms_compare(const Bitmapset *fc_a, const Bitmapset *fc_b)
{
	int			fc_shortlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
		return bms_is_empty(fc_b) ? 0 : -1;
	else if (fc_b == NULL)
		return bms_is_empty(fc_a) ? 0 : +1;
	/* 处理一个输入比另一个输入长的情况 */
	fc_shortlen = Min(fc_a->nwords, fc_b->nwords);
	for (fc_i = fc_shortlen; fc_i < fc_a->nwords; fc_i++)
	{
		if (fc_a->words[fc_i] != 0)
			return +1;
	}
	for (fc_i = fc_shortlen; fc_i < fc_b->nwords; fc_i++)
	{
		if (fc_b->words[fc_i] != 0)
			return -1;
	}
	/* 处理共同的单词 */
	fc_i = fc_shortlen;
	while (--fc_i >= 0)
	{
		bitmapword	fc_aw = fc_a->words[fc_i];
		bitmapword	fc_bw = fc_b->words[fc_i];

		if (fc_aw != fc_bw)
			return (fc_aw > fc_bw) ? +1 : -1;
	}
	return 0;
}

/* 
 * bms_make_singleton - 构建一个包含单个成员的位图集 
 */
Bitmapset * bms_make_singleton(int fc_x)
{
	Bitmapset  *fc_result;
	int			fc_wordnum,
				fc_bitnum;

	if (fc_x < 0)
		elog(ERROR, "negative bitmapset member not allowed");
	fc_wordnum = WORDNUM(fc_x);
	fc_bitnum = BITNUM(fc_x);
	fc_result = (Bitmapset *) palloc0(BITMAPSET_SIZE(fc_wordnum + 1));
	fc_result->nwords = fc_wordnum + 1;
	fc_result->words[fc_wordnum] = ((bitmapword) 1 << fc_bitnum);
	return fc_result;
}

/* 
 * bms_free - 释放一个位图集 
 * 
 * 和pfree相同，只是允许NULL输入 
 */
void bms_free(Bitmapset *fc_a)
{
	if (fc_a)
		pfree(fc_a);
}


/* 
 * 这些操作都生成一个新分配的结果， 
 * 保持它们的输入不变 
 */


/* 
 * bms_union - 集合并 
 */
Bitmapset * bms_union(const Bitmapset *fc_a, const Bitmapset *fc_b)
{
	Bitmapset  *fc_result;
	const Bitmapset *fc_other;
	int			fc_otherlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
		return bms_copy(fc_b);
	if (fc_b == NULL)
		return bms_copy(fc_a);
	/* 识别较短和较长的输入；复制较长的输入 */
	if (fc_a->nwords <= fc_b->nwords)
	{
		fc_result = bms_copy(fc_b);
		fc_other = fc_a;
	}
	else
	{
		fc_result = bms_copy(fc_a);
		fc_other = fc_b;
	}
	/* 并将较短的输入并入结果 */
	fc_otherlen = fc_other->nwords;
	for (fc_i = 0; fc_i < fc_otherlen; fc_i++)
		fc_result->words[fc_i] |= fc_other->words[fc_i];
	return fc_result;
}

/* 
 * bms_intersect - 集合交集 
 */
Bitmapset * bms_intersect(const Bitmapset *fc_a, const Bitmapset *fc_b)
{
	Bitmapset  *fc_result;
	const Bitmapset *fc_other;
	int			fc_resultlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL || fc_b == NULL)
		return NULL;
	/* 识别较短和较长的输入；复制较短的输入 */
	if (fc_a->nwords <= fc_b->nwords)
	{
		fc_result = bms_copy(fc_a);
		fc_other = fc_b;
	}
	else
	{
		fc_result = bms_copy(fc_b);
		fc_other = fc_a;
	}
	/* 并将较长的输入与结果交集 */
	fc_resultlen = fc_result->nwords;
	for (fc_i = 0; fc_i < fc_resultlen; fc_i++)
		fc_result->words[fc_i] &= fc_other->words[fc_i];
	return fc_result;
}

/* 
 * bms_difference - 集合差集（即，A去掉B的成员） 
 */
Bitmapset * bms_difference(const Bitmapset *fc_a, const Bitmapset *fc_b)
{
	Bitmapset  *fc_result;
	int			fc_shortlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
		return NULL;
	if (fc_b == NULL)
		return bms_copy(fc_a);
	/* 复制左侧输入 */
	fc_result = bms_copy(fc_a);
	/* 并从结果中去掉b的位 */
	fc_shortlen = Min(fc_a->nwords, fc_b->nwords);
	for (fc_i = 0; fc_i < fc_shortlen; fc_i++)
		fc_result->words[fc_i] &= ~fc_b->words[fc_i];
	return fc_result;
}

/* 
 * bms_is_subset - A是B的子集吗？ 
 */
bool bms_is_subset(const Bitmapset *fc_a, const Bitmapset *fc_b)
{
	int			fc_shortlen;
	int			fc_longlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
		return true;			/* 空集合是任何集合的子集 */
	if (fc_b == NULL)
		return bms_is_empty(fc_a);
	/* 检查共同的单词 */
	fc_shortlen = Min(fc_a->nwords, fc_b->nwords);
	for (fc_i = 0; fc_i < fc_shortlen; fc_i++)
	{
		if ((fc_a->words[fc_i] & ~fc_b->words[fc_i]) != 0)
			return false;
	}
	/* 检查额外的单词 */
	if (fc_a->nwords > fc_b->nwords)
	{
		fc_longlen = fc_a->nwords;
		for (; fc_i < fc_longlen; fc_i++)
		{
			if (fc_a->words[fc_i] != 0)
				return false;
		}
	}
	return true;
}

/* 
 * bms_subset_compare - 比较A和B的相等/子集关系 
 * 
 * 这比双向测试bms_is_subset更有效。 
 */
BMS_Comparison
bms_subset_compare(const Bitmapset *fc_a, const Bitmapset *fc_b)
{
	BMS_Comparison fc_result;
	int			fc_shortlen;
	int			fc_longlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
	{
		if (fc_b == NULL)
			return BMS_EQUAL;
		return bms_is_empty(fc_b) ? BMS_EQUAL : BMS_SUBSET1;
	}
	if (fc_b == NULL)
		return bms_is_empty(fc_a) ? BMS_EQUAL : BMS_SUBSET2;
	/* 检查共同的单词 */
	fc_result = BMS_EQUAL;			/* 到目前为止的状态 */
	fc_shortlen = Min(fc_a->nwords, fc_b->nwords);
	for (fc_i = 0; fc_i < fc_shortlen; fc_i++)
	{
		bitmapword	fc_aword = fc_a->words[fc_i];
		bitmapword	fc_bword = fc_b->words[fc_i];

		if ((fc_aword & ~fc_bword) != 0)
		{
			/* a不是b的子集 */
			if (fc_result == BMS_SUBSET1)
				return BMS_DIFFERENT;
			fc_result = BMS_SUBSET2;
		}
		if ((fc_bword & ~fc_aword) != 0)
		{
			/* b不是a的子集 */
			if (fc_result == BMS_SUBSET2)
				return BMS_DIFFERENT;
			fc_result = BMS_SUBSET1;
		}
	}
	/* 检查额外的单词 */
	if (fc_a->nwords > fc_b->nwords)
	{
		fc_longlen = fc_a->nwords;
		for (; fc_i < fc_longlen; fc_i++)
		{
			if (fc_a->words[fc_i] != 0)
			{
				/* a不是b的子集 */
				if (fc_result == BMS_SUBSET1)
					return BMS_DIFFERENT;
				fc_result = BMS_SUBSET2;
			}
		}
	}
	else if (fc_a->nwords < fc_b->nwords)
	{
		fc_longlen = fc_b->nwords;
		for (; fc_i < fc_longlen; fc_i++)
		{
			if (fc_b->words[fc_i] != 0)
			{
				/* b不是a的子集 */
				if (fc_result == BMS_SUBSET2)
					return BMS_DIFFERENT;
				fc_result = BMS_SUBSET1;
			}
		}
	}
	return fc_result;
}

/* 
 * bms_is_member - X是A的成员吗？ 
 */
bool bms_is_member(int fc_x, const Bitmapset *fc_a)
{
	int			fc_wordnum,
				fc_bitnum;

	/* XXX更好的是对于x<0只返回false？ */
	if (fc_x < 0)
		elog(ERROR, "negative bitmapset member not allowed");
	if (fc_a == NULL)
		return false;
	fc_wordnum = WORDNUM(fc_x);
	fc_bitnum = BITNUM(fc_x);
	if (fc_wordnum >= fc_a->nwords)
		return false;
	if ((fc_a->words[fc_wordnum] & ((bitmapword) 1 << fc_bitnum)) != 0)
		return true;
	return false;
}

/* 
 * bms_member_index 
 * 	 确定位图中成员x的0基索引 
 * 
 * 当x不是成员时返回(-1)。 
 */
int bms_member_index(Bitmapset *fc_a, int fc_x)
{
	int			fc_i;
	int			fc_bitnum;
	int			fc_wordnum;
	int			fc_result = 0;
	bitmapword	fc_mask;

	/* 如果不是位图的成员则返回-1 */
	if (!bms_is_member(fc_x, fc_a))
		return -1;

	fc_wordnum = WORDNUM(fc_x);
	fc_bitnum = BITNUM(fc_x);

	/* 计算前面的单词中的位 */
	for (fc_i = 0; fc_i < fc_wordnum; fc_i++)
	{
		bitmapword	fc_w = fc_a->words[fc_i];

		/* 不需要计算零单词中的位 */
		if (fc_w != 0)
			fc_result += bmw_popcount(fc_w);
	}

	/* 
	 * 现在添加最后一个单词的位，但只添加在项之前的那些。我们可以 
	 * 通过应用掩码然后再次使用popcount来做到这一点。为了得到 
	 * 0基索引，我们只想计算前面的位，而不是项 
	 * 本身，因此我们减去1。 
	 */
	fc_mask = ((bitmapword) 1 << fc_bitnum) - 1;
	fc_result += bmw_popcount(fc_a->words[fc_wordnum] & fc_mask);

	return fc_result;
}

/* 
 * bms_overlap - 集合是否重叠（即，是否有非空交集）？ 
 */
bool bms_overlap(const Bitmapset *fc_a, const Bitmapset *fc_b)
{
	int			fc_shortlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL || fc_b == NULL)
		return false;
	/* 检查共享词汇 */
	fc_shortlen = Min(fc_a->nwords, fc_b->nwords);
	for (fc_i = 0; fc_i < fc_shortlen; fc_i++)
	{
		if ((fc_a->words[fc_i] & fc_b->words[fc_i]) != 0)
			return true;
	}
	return false;
}

/*
 * bms_overlap_list - 一个集合是否与整数列表重叠？
 */
bool bms_overlap_list(const Bitmapset *fc_a, const List *fc_b)
{
	ListCell   *fc_lc;
	int			fc_wordnum,
				fc_bitnum;

	if (fc_a == NULL || fc_b == NIL)
		return false;

	foreach(fc_lc, fc_b)
	{
		int			fc_x = lfirst_int(fc_lc);

		if (fc_x < 0)
			elog(ERROR, "negative bitmapset member not allowed");
		fc_wordnum = WORDNUM(fc_x);
		fc_bitnum = BITNUM(fc_x);
		if (fc_wordnum < fc_a->nwords)
			if ((fc_a->words[fc_wordnum] & ((bitmapword) 1 << fc_bitnum)) != 0)
				return true;
	}

	return false;
}

/*
 * bms_nonempty_difference - 集合是否有非空差异？
 *
 * 即，'a'中的任何成员是否在'b'中也不存在。
 */
bool bms_nonempty_difference(const Bitmapset *fc_a, const Bitmapset *fc_b)
{
	int			fc_shortlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
		return false;
	if (fc_b == NULL)
		return !bms_is_empty(fc_a);
	/* 检查共享词汇 */
	fc_shortlen = Min(fc_a->nwords, fc_b->nwords);
	for (fc_i = 0; fc_i < fc_shortlen; fc_i++)
	{
		if ((fc_a->words[fc_i] & ~fc_b->words[fc_i]) != 0)
			return true;
	}
	/* 检查a中的额外单词 */
	for (; fc_i < fc_a->nwords; fc_i++)
	{
		if (fc_a->words[fc_i] != 0)
			return true;
	}
	return false;
}

/*
 * bms_singleton_member - 返回集合的唯一整数成员
 *
 * 如果|a|不是1则引发错误。
 */
int bms_singleton_member(const Bitmapset *fc_a)
{
	int			fc_result = -1;
	int			fc_nwords;
	int			fc_wordnum;

	if (fc_a == NULL)
		elog(ERROR, "bitmapset is empty");
	fc_nwords = fc_a->nwords;
	for (fc_wordnum = 0; fc_wordnum < fc_nwords; fc_wordnum++)
	{
		bitmapword	fc_w = fc_a->words[fc_wordnum];

		if (fc_w != 0)
		{
			if (fc_result >= 0 || HAS_MULTIPLE_ONES(fc_w))
				elog(ERROR, "bitmapset has multiple members");
			fc_result = fc_wordnum * BITS_PER_BITMAPWORD;
			fc_result += bmw_rightmost_one_pos(fc_w);
		}
	}
	if (fc_result < 0)
		elog(ERROR, "bitmapset is empty");
	return fc_result;
}

/*
 * bms_get_singleton_member
 *
 * 测试给定集合是否为唯一成员。
 * 如果是，将*member设置为其唯一成员的值，并返回true。
 * 如果不是，返回false，而不改变*member。
 *
 * 如果我们不关心区分空集合和多个成员的集合，这比调用bms_membership()和然后调用
 * bms_singleton_member()要更方便和快速。
 */
bool bms_get_singleton_member(const Bitmapset *fc_a, int *fc_member)
{
	int			fc_result = -1;
	int			fc_nwords;
	int			fc_wordnum;

	if (fc_a == NULL)
		return false;
	fc_nwords = fc_a->nwords;
	for (fc_wordnum = 0; fc_wordnum < fc_nwords; fc_wordnum++)
	{
		bitmapword	fc_w = fc_a->words[fc_wordnum];

		if (fc_w != 0)
		{
			if (fc_result >= 0 || HAS_MULTIPLE_ONES(fc_w))
				return false;
			fc_result = fc_wordnum * BITS_PER_BITMAPWORD;
			fc_result += bmw_rightmost_one_pos(fc_w);
		}
	}
	if (fc_result < 0)
		return false;
	*fc_member = fc_result;
	return true;
}

/*
 * bms_num_members - 计算集合的成员数量
 */
int bms_num_members(const Bitmapset *fc_a)
{
	int			fc_result = 0;
	int			fc_nwords;
	int			fc_wordnum;

	if (fc_a == NULL)
		return 0;
	fc_nwords = fc_a->nwords;
	for (fc_wordnum = 0; fc_wordnum < fc_nwords; fc_wordnum++)
	{
		bitmapword	fc_w = fc_a->words[fc_wordnum];

		/* 不需要计算零单词中的位 */
		if (fc_w != 0)
			fc_result += bmw_popcount(fc_w);
	}
	return fc_result;
}

/*
 * bms_membership - 一个集合是否有零、一个或多个成员？
 *
 * 这比使用bms_num_members()进行精确计数要快。
 */
BMS_Membership
bms_membership(const Bitmapset *fc_a)
{
	BMS_Membership fc_result = BMS_EMPTY_SET;
	int			fc_nwords;
	int			fc_wordnum;

	if (fc_a == NULL)
		return BMS_EMPTY_SET;
	fc_nwords = fc_a->nwords;
	for (fc_wordnum = 0; fc_wordnum < fc_nwords; fc_wordnum++)
	{
		bitmapword	fc_w = fc_a->words[fc_wordnum];

		if (fc_w != 0)
		{
			if (fc_result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(fc_w))
				return BMS_MULTIPLE;
			fc_result = BMS_SINGLETON;
		}
	}
	return fc_result;
}

/*
 * bms_is_empty - 一个集合是否为空？
 *
 * 这甚至比bms_membership()更快。
 */
bool bms_is_empty(const Bitmapset *fc_a)
{
	int			fc_nwords;
	int			fc_wordnum;

	if (fc_a == NULL)
		return true;
	fc_nwords = fc_a->nwords;
	for (fc_wordnum = 0; fc_wordnum < fc_nwords; fc_wordnum++)
	{
		bitmapword	fc_w = fc_a->words[fc_wordnum];

		if (fc_w != 0)
			return false;
	}
	return true;
}


/*
 * 这些操作都“回收”它们的非常量输入，即，要么
 * 返回修改后的输入，要么如果无法保存结果则释放它。
 *
 * 通常应该以这样的方式使用
 *
 *		foo = bms_add_member(foo, x);
 */


/*
 * bms_add_member - 向集合中添加指定成员
 *
 * 输入集合被修改或回收！
 */
Bitmapset * bms_add_member(Bitmapset *fc_a, int fc_x)
{
	int			fc_wordnum,
				fc_bitnum;

	if (fc_x < 0)
		elog(ERROR, "negative bitmapset member not allowed");
	if (fc_a == NULL)
		return bms_make_singleton(fc_x);
	fc_wordnum = WORDNUM(fc_x);
	fc_bitnum = BITNUM(fc_x);

	/* 如果有必要，扩大集合 */
	if (fc_wordnum >= fc_a->nwords)
	{
		int			fc_oldnwords = fc_a->nwords;
		int			fc_i;

		fc_a = (Bitmapset *) repalloc(fc_a, BITMAPSET_SIZE(fc_wordnum + 1));
		fc_a->nwords = fc_wordnum + 1;
		/* 将扩大的部分清零 */
		for (fc_i = fc_oldnwords; fc_i < fc_a->nwords; fc_i++)
			fc_a->words[fc_i] = 0;
	}

	fc_a->words[fc_wordnum] |= ((bitmapword) 1 << fc_bitnum);
	return fc_a;
}

/*
 * bms_del_member - 从集合中移除指定成员
 *
 * 如果x当前不是集合的成员则不会引发错误
 *
 * 输入集合原地修改！
 */
Bitmapset * bms_del_member(Bitmapset *fc_a, int fc_x)
{
	int			fc_wordnum,
				fc_bitnum;

	if (fc_x < 0)
		elog(ERROR, "negative bitmapset member not allowed");
	if (fc_a == NULL)
		return NULL;
	fc_wordnum = WORDNUM(fc_x);
	fc_bitnum = BITNUM(fc_x);
	if (fc_wordnum < fc_a->nwords)
		fc_a->words[fc_wordnum] &= ~((bitmapword) 1 << fc_bitnum);
	return fc_a;
}

/*
 * bms_add_members - 类似于bms_union，但左输入被回收
 */
Bitmapset * bms_add_members(Bitmapset *fc_a, const Bitmapset *fc_b)
{
	Bitmapset  *fc_result;
	const Bitmapset *fc_other;
	int			fc_otherlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
		return bms_copy(fc_b);
	if (fc_b == NULL)
		return fc_a;
	/* 识别较短和较长的输入；如果需要则复制较长的输入 */
	if (fc_a->nwords < fc_b->nwords)
	{
		fc_result = bms_copy(fc_b);
		fc_other = fc_a;
	}
	else
	{
		fc_result = fc_a;
		fc_other = fc_b;
	}
	/* 并将较短的输入并入结果 */
	fc_otherlen = fc_other->nwords;
	for (fc_i = 0; fc_i < fc_otherlen; fc_i++)
		fc_result->words[fc_i] |= fc_other->words[fc_i];
	if (fc_result != fc_a)
		pfree(fc_a);
	return fc_result;
}

/*
 * bms_add_range
 *		将范围从'lower'到'upper'的成员添加到集合中。
 *
 * 请注意，这也可以通过在循环中调用bms_add_member来完成，然而，
 * 当范围很大时，使用此函数将更快，因为我们在
 * bitmapword级别上工作，而不是位级别。
 */
Bitmapset * bms_add_range(Bitmapset *fc_a, int fc_lower, int fc_upper)
{
	int			fc_lwordnum,
				fc_lbitnum,
				fc_uwordnum,
				fc_ushiftbits,
				fc_wordnum;

	/* 如果没有调用请求则不执行任何操作，无需进一步检查 */
	if (fc_upper < fc_lower)
		return fc_a;

	if (fc_lower < 0)
		elog(ERROR, "negative bitmapset member not allowed");
	fc_uwordnum = WORDNUM(fc_upper);

	if (fc_a == NULL)
	{
		fc_a = (Bitmapset *) palloc0(BITMAPSET_SIZE(fc_uwordnum + 1));
		fc_a->nwords = fc_uwordnum + 1;
	}
	else if (fc_uwordnum >= fc_a->nwords)
	{
		int			fc_oldnwords = fc_a->nwords;
		int			fc_i;

		/* 确保我们有足够的字存储上层位 */
		fc_a = (Bitmapset *) repalloc(fc_a, BITMAPSET_SIZE(fc_uwordnum + 1));
		fc_a->nwords = fc_uwordnum + 1;
		/* 将扩大的部分清零 */
		for (fc_i = fc_oldnwords; fc_i < fc_a->nwords; fc_i++)
			fc_a->words[fc_i] = 0;
	}

	fc_wordnum = fc_lwordnum = WORDNUM(fc_lower);

	fc_lbitnum = BITNUM(fc_lower);
	fc_ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(fc_upper) + 1);

	/*
	 * 特殊情况当lwordnum与uwordnum相同时，我们必须在单词上执行
	 * 上层和下层的掩码。
	 */
	if (fc_lwordnum == fc_uwordnum)
	{
		fc_a->words[fc_lwordnum] |= ~(bitmapword) (((bitmapword) 1 << fc_lbitnum) - 1)
			& (~(bitmapword) 0) >> fc_ushiftbits;
	}
	else
	{
		/* 打开lbitnum及其左侧的所有位 */
		fc_a->words[fc_wordnum++] |= ~(bitmapword) (((bitmapword) 1 << fc_lbitnum) - 1);

		/* 打开任何中间单词的所有位 */
		while (fc_wordnum < fc_uwordnum)
			fc_a->words[fc_wordnum++] = ~(bitmapword) 0;

		/* 打开upper的位及其右侧的所有位。 */
		fc_a->words[fc_uwordnum] |= (~(bitmapword) 0) >> fc_ushiftbits;
	}

	return fc_a;
}

/*
 * bms_int_members - 类似于bms_intersect，但左输入被回收
 */
Bitmapset * bms_int_members(Bitmapset *fc_a, const Bitmapset *fc_b)
{
	int			fc_shortlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
		return NULL;
	if (fc_b == NULL)
	{
		pfree(fc_a);
		return NULL;
	}
	/* 将b与a相交；我们无需复制 */
	fc_shortlen = Min(fc_a->nwords, fc_b->nwords);
	for (fc_i = 0; fc_i < fc_shortlen; fc_i++)
		fc_a->words[fc_i] &= fc_b->words[fc_i];
	for (; fc_i < fc_a->nwords; fc_i++)
		fc_a->words[fc_i] = 0;
	return fc_a;
}

/*
 * bms_del_members - 类似于bms_difference，但左输入被回收
 */
Bitmapset * bms_del_members(Bitmapset *fc_a, const Bitmapset *fc_b)
{
	int			fc_shortlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
		return NULL;
	if (fc_b == NULL)
		return fc_a;
	/* 从a中移除b的位；我们无需复制 */
	fc_shortlen = Min(fc_a->nwords, fc_b->nwords);
	for (fc_i = 0; fc_i < fc_shortlen; fc_i++)
		fc_a->words[fc_i] &= ~fc_b->words[fc_i];
	return fc_a;
}

/*
 * bms_join - 类似于bms_union，但*两个*输入都被回收
 */
Bitmapset * bms_join(Bitmapset *fc_a, Bitmapset *fc_b)
{
	Bitmapset  *fc_result;
	Bitmapset  *fc_other;
	int			fc_otherlen;
	int			fc_i;

	/* 处理任一输入为NULL的情况 */
	if (fc_a == NULL)
		return fc_b;
	if (fc_b == NULL)
		return fc_a;
	/* 识别较短和较长的输入；使用较长的作为结果 */
	if (fc_a->nwords < fc_b->nwords)
	{
		fc_result = fc_b;
		fc_other = fc_a;
	}
	else
	{
		fc_result = fc_a;
		fc_other = fc_b;
	}
	/* 并将较短的输入并入结果 */
	fc_otherlen = fc_other->nwords;
	for (fc_i = 0; fc_i < fc_otherlen; fc_i++)
		fc_result->words[fc_i] |= fc_other->words[fc_i];
	if (fc_other != fc_result)		/* 纯粹的偏执 */
		pfree(fc_other);
	return fc_result;
}

/*
 * bms_first_member - 查找并移除集合的第一个成员
 *
 * 如果集合为空则返回-1。注意：集合被破坏性修改！
 *
 * 这旨在支持通过集合成员进行迭代。
 * 典型模式是
 *
 *			while ((x = bms_first_member(inputset)) >= 0)
 *			 处理成员x；
 *
 * 注意：这会破坏“inputset”的内容。如果集合不得修改，请使用bms_next_member代替。
 */
int bms_first_member(Bitmapset *fc_a)
{
	int			fc_nwords;
	int			fc_wordnum;

	if (fc_a == NULL)
		return -1;
	fc_nwords = fc_a->nwords;
	for (fc_wordnum = 0; fc_wordnum < fc_nwords; fc_wordnum++)
	{
		bitmapword	fc_w = fc_a->words[fc_wordnum];

		if (fc_w != 0)
		{
			int			fc_result;

			fc_w = RIGHTMOST_ONE(fc_w);
			fc_a->words[fc_wordnum] &= ~fc_w;

			fc_result = fc_wordnum * BITS_PER_BITMAPWORD;
			fc_result += bmw_rightmost_one_pos(fc_w);
			return fc_result;
		}
	}
	return -1;
}

/*
 * bms_next_member - 查找集合的下一个成员
 *
 * 返回大于“prevbit”的最小成员，如果没有则返回-2。
 * “prevbit”必须 NOT 小于 -1，否则行为不可预测。
 *
 * 这用于支持遍历集合的成员。
 * 通常的模式是
 *
 *			x = -1;
 *			while ((x = bms_next_member(inputset, x)) >= 0)
 *			 处理成员 x;
 *
 * 注意，当没有更多成员时，我们返回 -2，而不是 -1，如你所期望的。
 * 这样做的理由是为了区分循环未开始状态（x == -1）和循环完成状态（x == -2）。
 * 在简单的循环用法中没有区别，但复杂的迭代逻辑可能需要这样的能力。
 */
int bms_next_member(const Bitmapset *fc_a, int fc_prevbit)
{
	int			fc_nwords;
	int			fc_wordnum;
	bitmapword	fc_mask;

	if (fc_a == NULL)
		return -2;
	fc_nwords = fc_a->nwords;
	fc_prevbit++;
	fc_mask = (~(bitmapword) 0) << BITNUM(fc_prevbit);
	for (fc_wordnum = WORDNUM(fc_prevbit); fc_wordnum < fc_nwords; fc_wordnum++)
	{
		bitmapword	fc_w = fc_a->words[fc_wordnum];

		/* 忽略 prevbit 之前的位 */
		fc_w &= fc_mask;

		if (fc_w != 0)
		{
			int			fc_result;

			fc_result = fc_wordnum * BITS_PER_BITMAPWORD;
			fc_result += bmw_rightmost_one_pos(fc_w);
			return fc_result;
		}

		/* 在后续字中，考虑所有位 */
		fc_mask = (~(bitmapword) 0);
	}
	return -2;
}

/*
 * bms_prev_member - 查找集合的前一个成员
 *
 * 返回小于“prevbit”的最大成员，如果没有则返回-2。
 * “prevbit”必须 NOT 大于当前大小的 Bitmapset 中可能设置的最高位加一。
 *
 * 为了简化初始循环中寻找最高设置位的过程，可以传递特殊的 prevbit 值 -1，
 * 以让函数找到集合中值最高的成员。
 *
 * 这用于支持反向遍历集合的成员。
 * 通常的模式是
 *
 *			x = -1;
 *			while ((x = bms_prev_member(inputset, x)) >= 0)
 *			 处理成员 x;
 *
 * 注意，当没有更多成员时，我们返回 -2，而不是 -1，如你所期望的。
 * 这样做的理由是为了区分循环未开始状态（x == -1）和循环完成状态（x == -2）。
 * 在简单的循环用法中没有区别，但复杂的迭代逻辑可能需要这样的能力。
 */

int bms_prev_member(const Bitmapset *fc_a, int fc_prevbit)
{
	int			fc_wordnum;
	int			fc_ushiftbits;
	bitmapword	fc_mask;

	/*
	 * 如果集合为 NULL 或者右侧没有更多位，我们就没有什么可以做的。
	 */
	if (fc_a == NULL || fc_prevbit == 0)
		return -2;

	/* 将 -1 转换为我们可以设置的最高可能位 */
	if (fc_prevbit == -1)
		fc_prevbit = fc_a->nwords * BITS_PER_BITMAPWORD - 1;
	else
		fc_prevbit--;

	fc_ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(fc_prevbit) + 1);
	fc_mask = (~(bitmapword) 0) >> fc_ushiftbits;
	for (fc_wordnum = WORDNUM(fc_prevbit); fc_wordnum >= 0; fc_wordnum--)
	{
		bitmapword	fc_w = fc_a->words[fc_wordnum];

		/* 掩蔽出 prevbit 左侧的位 */
		fc_w &= fc_mask;

		if (fc_w != 0)
		{
			int			fc_result;

			fc_result = fc_wordnum * BITS_PER_BITMAPWORD;
			fc_result += bmw_leftmost_one_pos(fc_w);
			return fc_result;
		}

		/* 在后续字中，考虑所有位 */
		fc_mask = (~(bitmapword) 0);
	}
	return -2;
}

/*
 * bms_hash_value - 计算 Bitmapset 的哈希键
 *
 * 注意：我们必须确保任何两个 bms_equal() 的 Bitmapset
 * 哈希到相同的值；实际中这意味着尾随的全零字必须不影响结果。 
 * 因此在应用 hash_any() 之前我们会去除它们。
 */
uint32 bms_hash_value(const Bitmapset *fc_a)
{
	int			fc_lastword;

	if (fc_a == NULL)
		return 0;				/* 所有空集合的哈希值为 0 */
	for (fc_lastword = fc_a->nwords; --fc_lastword >= 0;)
	{
		if (fc_a->words[fc_lastword] != 0)
			break;
	}
	if (fc_lastword < 0)
		return 0;				/* 所有空集合的哈希值为 0 */
	return DatumGetUInt32(hash_any((const unsigned char *) fc_a->words,
								   (fc_lastword + 1) * sizeof(bitmapword)));
}

/*
 * bitmap_hash - 用于（指向）Bitmapsets 的哈希函数
 *
 * 注意：不要忘记指定 bitmap_match 作为匹配函数！
 */
uint32 bitmap_hash(const void *fc_key, Size fc_keysize)
{
	Assert(fc_keysize == sizeof(Bitmapset *));
	return bms_hash_value(*((const Bitmapset *const *) fc_key));
}

/*
 * bitmap_match - 用于 bitmap_hash 的匹配函数
 */
int bitmap_match(const void *fc_key1, const void *fc_key2, Size fc_keysize)
{
	Assert(fc_keysize == sizeof(Bitmapset *));
	return !bms_equal(*((const Bitmapset *const *) fc_key1),
					  *((const Bitmapset *const *) fc_key2));
}
